{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Select Buildings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #选择建筑的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的二进制字符串&nbsp;<code>s</code>&nbsp;，它表示一条街沿途的建筑类型，其中：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>s[i] = '0'</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;栋建筑是一栋办公楼，</li>\n",
    "\t<li><code>s[i] = '1'</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;栋建筑是一间餐厅。</li>\n",
    "</ul>\n",
    "\n",
    "<p>作为市政厅的官员，你需要随机<strong>&nbsp;选择</strong>&nbsp;3 栋建筑。然而，为了确保多样性，选出来的 3 栋建筑 <strong>相邻</strong>&nbsp;的两栋不能是同一类型。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，给你&nbsp;<code>s = \"0<em><strong>0</strong></em>1<em><strong>1</strong></em>0<em><strong>1</strong></em>\"</code>&nbsp;，我们不能选择第&nbsp;<code>1</code>&nbsp;，<code>3</code>&nbsp;和&nbsp;<code>5</code>&nbsp;栋建筑，因为得到的子序列是&nbsp;<code>\"0<em><strong>11</strong></em>\"</code>&nbsp;，有相邻两栋建筑是同一类型，所以 <strong>不合</strong>&nbsp;题意。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回可以选择 3 栋建筑的 <strong>有效方案数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"001101\"\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>\n",
    "以下下标集合是合法的：\n",
    "- [0,2,4] ，从 \"<em><strong>0</strong></em>0<em><strong>1</strong></em>1<em><strong>0</strong></em>1\" 得到 \"010\"\n",
    "- [0,3,4] ，从 \"<em><strong>0</strong></em>01<em><strong>10</strong></em>1\" 得到 \"010\"\n",
    "- [1,2,4] ，从 \"0<em><strong>01</strong></em>1<em><strong>0</strong></em>1\" 得到 \"010\"\n",
    "- [1,3,4] ，从 \"0<em><strong>0</strong></em>1<em><strong>10</strong></em>1\" 得到 \"010\"\n",
    "- [2,4,5] ，从 \"00<em><strong>1</strong></em>1<em><strong>01</strong></em>\" 得到 \"101\"\n",
    "- [3,4,5] ，从 \"001<em><strong>101</strong></em>\" 得到 \"101\"\n",
    "没有别的合法选择，所以总共有 6 种方法。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"11100\"\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>没有任何符合题意的选择。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code>&nbsp;要么是&nbsp;<code>'0'</code>&nbsp;，要么是&nbsp;<code>'1'</code>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-select-buildings](https://leetcode.cn/problems/number-of-ways-to-select-buildings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-select-buildings](https://leetcode.cn/problems/number-of-ways-to-select-buildings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"001101\"', '\"11100\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        \n",
    "        M = 10 ** 9 + 7\n",
    "        \n",
    "        @cache\n",
    "        def dp(cur, k):\n",
    "            if abs(cur - endPos) > k:\n",
    "                return 0\n",
    "            if not k:\n",
    "                return cur == endPos\n",
    "            \n",
    "            return (dp(cur-1, k-1) + dp(cur+1, k-1)) % M\n",
    "        \n",
    "        \n",
    "        return dp(startPos, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        distance = abs(startPos - endPos)\n",
    "        if distance > k or (k - distance) % 2 != 0:\n",
    "            return 0\n",
    "\n",
    "        extra_steps = (k - distance) // 2\n",
    "        a = extra_steps\n",
    "        b = distance + extra_steps\n",
    "        return (factorial(a+b) // (factorial(a) * factorial(b))) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, a: int, b: int, k: int) -> int:\n",
    "        if a>b:\n",
    "            a,b=b,a\n",
    "        if b-a>k:\n",
    "            return 0\n",
    "        if (b-a)%2!=k%2:\n",
    "            return 0\n",
    "        return comb(k,(k-(b-a))//2)%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        # 如果直接考虑的话，这个状态就是startpos,endpos,k三者决定的，但是我觉得是由二者的差值决定的。\n",
    "        # 当差值一定的情况下，构造k*k大小的dp就完全够用了\n",
    "        dp = [[0]*(k+1) for _ in range(k+1)]\n",
    "        \n",
    "        for j in range(1,len(dp[0])):\n",
    "            # 不一定是1，它的个数是左挑和又跳的组合，考虑组合数\n",
    "            if j%2 == 0:\n",
    "                dp[0][j] = math.comb(j,j//2)%(10**9+7)\n",
    "        \n",
    "        # 初始处理\n",
    "        for i in range(len(dp)):\n",
    "            dp[i][i] = 1\n",
    "\n",
    "        for cha in range(1,len(dp)-1):\n",
    "            for j in range(cha+1,len(dp[0])):\n",
    "                dp[j-cha][j] = (dp[j-cha+1][j-1] + dp[j-cha-1][j-1])%(10**9+7)\n",
    "        \n",
    "        # for i in dp:\n",
    "        #     print(i)\n",
    "        if abs(startPos-endPos) > k:\n",
    "            return 0\n",
    "        return dp[abs(startPos-endPos)][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        d = abs(endPos - startPos) \n",
    "        if k < d or (k - d) % 2 != 0:\n",
    "            return 0 \n",
    "        mod = int(1e9 + 7)\n",
    "        x = (k - d) // 2 \n",
    "\n",
    "        f = []\n",
    "        for i in range( k+1):\n",
    "            f.append([0] * (i+1))\n",
    "            for j in range(i+1):\n",
    "                if j == 0 or j == i:\n",
    "                    f[i][j] = 1\n",
    "                else:\n",
    "                    f[i][j] = (f[i-1][j] + f[i-1][j-1]) % mod \n",
    "        \n",
    "        return f[k][x] \n",
    "    \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        n=abs(endPos-startPos)\n",
    "        if n%2!=k%2:\n",
    "            return 0\n",
    "        if n>k:\n",
    "            return 0\n",
    "        r=(k-n)//2\n",
    "        if r==0:\n",
    "            return 1\n",
    "        mod=10**9+7\n",
    "        f=[[0 for _ in range(r+1)]for _ in range(k+1)]\n",
    "        for i in range(1,k+1):\n",
    "            f[i][1]=i\n",
    "        for i in range(1,r):\n",
    "            f[i][i]=1\n",
    "        for i in range(2,k+1):\n",
    "            for j in range(2,min(i+1,r+1)):\n",
    "                f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod\n",
    "        print(f)\n",
    "        return f[k][r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: int, e: int, k: int) -> int:\n",
    "        if abs(s - e) > k:\n",
    "            return 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        dis = abs(s - e)\n",
    "        if dis + k & 1:\n",
    "            return 0\n",
    "        @cache\n",
    "        def dfs(d, u):\n",
    "            if u == d == 0:\n",
    "                return 1\n",
    "            if d < 0:\n",
    "                return dfs(-d, u)\n",
    "            if d > u:\n",
    "                return 0\n",
    "            return (dfs(d + 1, u - 1) + dfs(d - 1, u - 1)) % mod\n",
    "        res = dfs(dis, k)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        startPos=1000+startPos\n",
    "        endPos=1000+endPos\n",
    "        dp=[[0 for _ in range(startPos+k+2)] for _ in range(k+1)]\n",
    "        dp[0][startPos]=1\n",
    "        mod=int(1e9+7)\n",
    "        for i in range(k):\n",
    "            for j in range(startPos-k,startPos+k+1):\n",
    "                dp[i+1][j]=(dp[i][j-1]+dp[i][j+1])%mod\n",
    "        if endPos>k+startPos:\n",
    "            return 0\n",
    "        return dp[k][endPos]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        # r=(e-s+k)//2\n",
    "        # l=(s-e+k)//2\n",
    "        MOD = 10 ** 9 + 7\n",
    "        N = 2010\n",
    "        M = 1010 \n",
    "        dp=[[0]*N for i in range(k)]\n",
    "        diff = abs(startPos - endPos)\n",
    "        s = 1000  \n",
    "        e = 1000 + diff\n",
    "        dp=[[0]*3005 for i in range(1005)]\n",
    "        dp[1][s+1] = 1 # 走一步到s+1的方法是:向右1步\n",
    "        dp[1][s-1] = 1 # 走一步到s-1的方法是:向左1步\n",
    "        for i in range(2,k+1):# 一共可以走k步\n",
    "            for j in range(s-k,s+k+1): # 可以到达的范围是【s-k,s+k】\n",
    "                dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%MOD\n",
    "\n",
    "\n",
    "\n",
    "        return dp[k][e]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if abs(endPos-startPos)>k:\n",
    "            return 0\n",
    "        if abs(endPos-startPos)==k:\n",
    "            return 1\n",
    "        else:\n",
    "            a=0\n",
    "            b=endPos-startPos+k\n",
    "            dp=[[0]*(2*k+1) for _ in range(k+1)]\n",
    "            #dp[i][j]为第i步到达数轴上j位置的方法数\n",
    "            dp[0][k]=1\n",
    "            if k>=2:\n",
    "                for m in range(-k,k+1,1):\n",
    "                    if m!=0:\n",
    "                        dp[0][m+k]=0\n",
    "            for i in range(1,k+1):\n",
    "                for j in range(-k+1,k,1):\n",
    "                    if j-1>=-k+1:\n",
    "                        dp[i][j+k]+=dp[i-1][j-1+k]\n",
    "                    if j+1<= k-1:\n",
    "                        dp[i][j+k]+=dp[i-1][j+1+k]\n",
    "        return dp[k][b]%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        lower = min(startPos - k, endPos - k)\n",
    "        upper = max(startPos + k, endPos + k)\n",
    "        n = upper - lower + 1\n",
    "        dp = [[0] * (k + 1) for _ in range(n)]\n",
    "        dp[startPos - lower][0] = 1\n",
    "        for j in range(1, k + 1):\n",
    "            dp[0][j] = dp[1][j - 1]\n",
    "            dp[n - 1][j] = dp[n - 2][j - 1]\n",
    "            for i in range(1, n - 1):\n",
    "                dp[i][j] = dp[i - 1][j - 1] + dp[i + 1][j - 1]\n",
    "        return dp[endPos - lower][k] % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        dp = [[0 for _ in range(2005)] for _ in range(1005)]\n",
    "        target = abs(startPos - endPos) + 1001\n",
    "\n",
    "        mod = 1e9+7\n",
    "        dp[0][1001] = 1\n",
    "        for i in range(1, k+1):\n",
    "            for j in range(1, 2002):\n",
    "                dp[i][j]= (dp[i-1][j-1] + dp[i-1][j+1]) % mod\n",
    "        return int(dp[k][target])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numberOfWays(self, start: int, ed: int, k: int) -> int:\r\n",
    "        mod = 10**9 + 7\r\n",
    "        dp = [[0] * 3050 for _ in range(0, 3010)]\r\n",
    "        start += 1000\r\n",
    "        ed += 1000\r\n",
    "        dp[0][start] = 1\r\n",
    "        dp[1][start + 1] = 1\r\n",
    "        dp[1][start - 1] = 1\r\n",
    "        for i in range(1, k + 1):\r\n",
    "            for j in range(1, 3010):\r\n",
    "                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod\r\n",
    "        return dp[k][ed]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.cache = {}\n",
    "\n",
    "    def f(self, left1, left2, startPos) -> int:\n",
    "        result = None\n",
    "        key =\"{0}+{1}\".format(left1, left2)\n",
    "        if key in self.cache:\n",
    "            result = self.cache[key]\n",
    "        elif left2 < 1:\n",
    "            result = 0\n",
    "        elif left2 == 1 and (left1 == startPos + 1 or left1 == startPos - 1):\n",
    "            result = 1\n",
    "        else:\n",
    "            result = self.f(left1 - 1, left2 - 1, startPos) + self.f(\n",
    "                left1 + 1, left2 - 1, startPos)\n",
    "        self.cache[key] = result\n",
    "        return result\n",
    "\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        return self.f(endPos, k, startPos) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, re):\n",
    "            if re == 0:\n",
    "                return 1 if idx == endPos else 0\n",
    "            return (dfs(idx + 1, re - 1) + dfs(idx - 1, re - 1)) % kmod\n",
    "        \n",
    "        ans = dfs(startPos, k)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if abs(endPos - startPos) == k and k > 0:\n",
    "            return 1\n",
    "        ans = 0\n",
    "        MOD = (10**9+7)\n",
    "        @cache\n",
    "        def dfs(index, step):\n",
    "            #print(index, step)\n",
    "            nonlocal ans\n",
    "            res = 0\n",
    "            if index == endPos and step == k:\n",
    "                #ans += 1\n",
    "                res += 1\n",
    "            for i in [-1, 1]:\n",
    "                if step + 1 <= k:\n",
    "                    res += dfs(index + i, step + 1)\n",
    "            return res % MOD\n",
    "        return dfs(startPos, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if abs(endPos - startPos) == k and k > 0:\n",
    "            return 1\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(index: int, steps: int) -> int:\n",
    "            ans, mod = 0, 10 ** 9 + 7\n",
    "\n",
    "            if index == endPos and steps == k:\n",
    "                ans += 1\n",
    "            for s in [-1, 1]:\n",
    "                if steps + 1 <= k:\n",
    "                    ans += dfs(index + s, steps + 1)\n",
    "            \n",
    "            return ans % mod\n",
    "        \n",
    "        return dfs(startPos, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        @cache\n",
    "        def df(n, k):\n",
    "            if n % 2 != k % 2:\n",
    "                return 0\n",
    "            if k < n:\n",
    "                return 0\n",
    "            if k == n:\n",
    "                return 1\n",
    "            \n",
    "            if n == 0:\n",
    "                return (df(1, k - 1) * 2) % (10**9+7)\n",
    "            else:\n",
    "                return (df(n - 1, k - 1) + df(n + 1, k - 1)) % (10**9+7)\n",
    "        a, b = min(startPos, endPos), max(startPos, endPos)\n",
    "        return df(b - a, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        smallest, biggest = endPos - k, endPos + k\n",
    "        d = [[-1 for _ in range(k + 10)] for _ in range(2 * k + 10)]\n",
    "\n",
    "        for i in range(2 * k + 10):\n",
    "            d[i][0] = 0\n",
    "\n",
    "        d[startPos - smallest][0] = 1\n",
    "\n",
    "        for step in range(1, k + 1):\n",
    "            for nums in range(1, 2 * k + 9):\n",
    "                d[nums][step] = d[nums - 1][step - 1] + d[nums + 1][step - 1]\n",
    "\n",
    "        return d[endPos - smallest][k] % int((10 ** 9 + 7))\n",
    "\n",
    "    \n",
    "    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        md = int(1e9 + 7)\n",
    "        dc = {}\n",
    "        def dfs(sp, ep, k):\n",
    "            v = '{}|{}|{}'.format(sp, ep, k)\n",
    "            if not k or k < abs(sp - ep) or (sp - ep) & 1 != k & 1:\n",
    "                return 0\n",
    "            if k == abs(sp - ep):\n",
    "                return 1\n",
    "            if dc.get(v):\n",
    "                return dc[v]\n",
    "            n1, n2 = dfs(sp - 1, ep, k - 1), dfs(sp + 1, ep, k - 1)\n",
    "            dc[v] = (n1 + n2) % md\n",
    "            return dc[v]\n",
    "        return dfs(startPos, endPos, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        #  time: O()\n",
    "        # space: O()\n",
    "        \n",
    "        seen = {}\n",
    "        def func(d, k):    # 距离 d 且有 k 步的情况下的方案总数\n",
    "            if d > k:\n",
    "                return 0\n",
    "            if d == k:\n",
    "                return 1\n",
    "            if (d, k) not in seen:\n",
    "                if not d:\n",
    "                    res = 0 if k % 2 else func(1, k-1) * 2\n",
    "                else:\n",
    "                    res = func(d+1, k-1) + func(d-1, k-1)\n",
    "                seen[d, k] = res % mod\n",
    "            return seen[d, k]\n",
    "        \n",
    "        mod = 10**9 + 7\n",
    "        return func(abs(startPos - endPos), k)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i > j or j < 0:\n",
    "                return 0\n",
    "            if j == 0:\n",
    "                return 1 if i == 0 else 0\n",
    "            return (dfs(i + 1, j - 1) + dfs(abs(i - 1), j - 1)) % mod\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        return dfs(abs(startPos - endPos), k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        dp = [{x:0 for x in range(startPos-k, startPos+k+1)} for _ in range(k+1)]\n",
    "        dp[0][endPos] = 1\n",
    "        for i in range(1, k+1):\n",
    "            for x in range(startPos-k+1, startPos+k):\n",
    "                dp[i][x] = dp[i-1][x-1] + dp[i-1][x+1]\n",
    "        return dp[k][startPos] % (10**9 + 7)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD= 10**9 + 7\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if startPos + k < endPos:\n",
    "            return 0\n",
    "        \n",
    "        if (k - endPos + startPos) & 1:\n",
    "            return 0\n",
    "        \n",
    "        left = (k - endPos + startPos) // 2\n",
    "        right = k - left\n",
    "        \n",
    "        res = 0\n",
    "        \n",
    "        @cache\n",
    "        def helper(l, r):\n",
    "            if l == r == 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            if l:\n",
    "                res += helper(l - 1, r)\n",
    "            if r:\n",
    "                res += helper(l, r - 1)\n",
    "            return res % MOD\n",
    "        \n",
    "        return helper(left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        s, e = min(startPos, endPos), max(startPos, endPos)\n",
    "        d = e - s\n",
    "        if k < d or (k - d) % 2 != 0:\n",
    "            return 0\n",
    "        l, r = d + (k - d) // 2, (k - d) // 2\n",
    "        mod = 10 ** 9 + 7\n",
    "        @ cache\n",
    "        def comb(m, n):\n",
    "            if n > m:\n",
    "                return 0\n",
    "            if n == 0 or n == m:\n",
    "                return 1\n",
    "            return (comb(m - 1, n - 1) + comb(m - 1, n)) % mod\n",
    "        return comb(l + r, r)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if (k - (endPos - startPos)) & 1 or k < abs(endPos - startPos):\n",
    "            return 0\n",
    "\n",
    "        @cache\n",
    "        def f(m, n):\n",
    "            if n == 0 or n == m:\n",
    "                return 1\n",
    "            return (f(m - 1, n) % MOD + f(m - 1, n - 1) % MOD) % MOD\n",
    "\n",
    "        return f(k, (k - (endPos - startPos)) // 2 + (endPos - startPos))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        end = abs(startPos - endPos)\n",
    "        if end > k or (k - end) & 1:\n",
    "            return 0\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def f(p: int, k: int) -> int:\n",
    "            \"\"\"位置 p, 剩余步数 k, 从 p 往 0 走\"\"\"\n",
    "            if abs(p) > k:\n",
    "                return 0\n",
    "            if k == 0 and p == 0:\n",
    "                return 1\n",
    "            return (f(p - 1, k - 1) + f(p + 1, k - 1)) % mod\n",
    "\n",
    "        return f(end, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        # 奇偶性\n",
    "        if (endPos - startPos) % 2 and k % 2 == 0:\n",
    "            return 0\n",
    "        if (endPos - startPos) % 2 == 0 and k % 2:\n",
    "            return 0\n",
    "        if (endPos - startPos) > k:\n",
    "            return 0\n",
    "        MOD = 1000000007\n",
    "        @cache\n",
    "        def dfs(i: int, now: int) -> int:\n",
    "            if abs(endPos - now) == (k - i):\n",
    "                return 1\n",
    "            if abs(endPos - now) > (k - i):\n",
    "                return 0\n",
    "            if i == k:\n",
    "                return int(now == endPos)\n",
    "            # 往左\n",
    "            res = dfs(i + 1, now - 1)\n",
    "            \n",
    "            # 往右\n",
    "            res += dfs(i + 1, now + 1) \n",
    "            return res % MOD\n",
    "        \n",
    "        return dfs(0, startPos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod=10**9+7\n",
    "\n",
    "        if (k-(endPos-startPos))%2!=0:\n",
    "            return 0\n",
    "        \n",
    "        ans=0\n",
    "        @cache\n",
    "        def dfs(i,r):\n",
    "            d=abs(endPos-i)\n",
    "            if r<d:\n",
    "                return 0\n",
    "           \n",
    "            if i==endPos and r==0:\n",
    "                return 1\n",
    "        \n",
    "            return (dfs(i-1,r-1)+dfs(i+1,r-1))%mod\n",
    "            \n",
    "        \n",
    "        return dfs(startPos,k)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "\n",
    "        cache = {}\n",
    "\n",
    "        def dfs(self, startPos, endPos, k):\n",
    "            if (startPos, k) in cache:\n",
    "                return cache[(startPos, k)]\n",
    "            result = 0\n",
    "            distance = abs(endPos - startPos)\n",
    "            if k < distance or ((k - distance) % 2 != 0):\n",
    "                return result\n",
    "            if k == distance:\n",
    "                return 1\n",
    "            result = result + dfs(self, startPos - 1, endPos, k - 1)\n",
    "            result = result + dfs(self, startPos + 1, endPos, k - 1)\n",
    "            cache[(startPos, k)] = result\n",
    "            return int(result % (10**9 + 7))\n",
    "\n",
    "        return dfs(self,startPos, endPos, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        y = k + endPos - startPos\n",
    "        x = k - endPos + startPos\n",
    "        if y & 1 or x & 1 or x < 0 or y < 0:\n",
    "            return 0\n",
    "\n",
    "        MOD = 10**9 + 7\n",
    "        # print(x, y)\n",
    "        # return math.comb((x + y)//2, x//2) % MOD\n",
    "\n",
    "        # L R\n",
    "        # R - L = endPos - startPos\n",
    "        # R + L = k\n",
    "        # 2R = k + endPos -startPos \n",
    "        # 2L = k - endPos + startPos\n",
    "        # dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        @cache\n",
    "        def helper(i, j) -> int:\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            if j == 0:\n",
    "                return 1\n",
    "            return helper(i-1, j) + helper(i, j-1)\n",
    "        return helper(x//2, y//2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def rec(n,m):\n",
    "            if m == n:\n",
    "                return 1\n",
    "            elif m == 1:\n",
    "                return n\n",
    "            else:\n",
    "                return rec(n-1,m-1)+rec(n-1,m)\n",
    "        n = endPos - startPos\n",
    "        if k < abs(n):\n",
    "            return 0\n",
    "        if k == abs(n):\n",
    "            return 1\n",
    "        if (k + n) % 2: \n",
    "            return 0\n",
    "        m = (k + n)//2\n",
    "        return  rec(k, m) % (10**9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def comb(k, b):\n",
    "            if b == 0 or b == k:\n",
    "                return 1\n",
    "            return comb(k -1, b) + comb(k - 1, b - 1)\n",
    "\n",
    "        a = abs(startPos - endPos)\n",
    "        if a > k:\n",
    "            return 0 \n",
    "        b = k - a \n",
    "        if b & 1:\n",
    "            return 0\n",
    "        return comb(k, b // 2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        dp = [[-1 for i in range(1001)] for j in range(3001)]\n",
    "        def dfs(pos,step):\n",
    "            if dp[pos+1000][step] > -1:\n",
    "                return dp[pos+1000][step]\n",
    "            if abs(pos-endPos) > step:\n",
    "                return 0\n",
    "            if step == 0:\n",
    "                return 1\n",
    "            dp[pos+1000][step] = (dfs(pos-1,step-1) + dfs(pos+1,step-1))%1000000007\n",
    "            return dp[pos+1000][step]\n",
    "        return dfs(startPos,k)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos, endPos, k):\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def f(x, left):\n",
    "            if abs(x - endPos) > left: return 0\n",
    "            if left == 0: return 1  # 成功到达终点，算一种方案\n",
    "            return (f(x - 1, left - 1) + f(x + 1, left - 1)) % MOD\n",
    "        return f(startPos, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 1e9 + 7\n",
    "        @cache\n",
    "        def dfs(i, step):\n",
    "            if abs(endPos - i) > step:\n",
    "                return 0\n",
    "            if step == 0:\n",
    "                return 1 \n",
    "            return (dfs(i-1,step-1) + dfs(i+1,step-1))%mod\n",
    "        return int(dfs(startPos,k) % mod)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        # 想不到状态转移的办法\n",
    "        # 搜索\n",
    "\n",
    "        @cache\n",
    "        def dfs(start, end, res):\n",
    "\n",
    "            if abs(end - start) > res:\n",
    "                return 0\n",
    "\n",
    "            if res == 0:\n",
    "                return 1 if start == end else 0\n",
    "            return (dfs(start - 1, end, res - 1) + dfs(start + 1, end, res - 1)) % (1e9 + 7)\n",
    "        \n",
    "        return int(dfs(startPos, endPos, k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        @cache\n",
    "        def move(s, e, k):\n",
    "            dis = abs(e - s)\n",
    "            if dis == k:\n",
    "                return 1\n",
    "            if dis > k or dis % 2 == 0 and k % 2 == 1 or dis % 2 == 1 and k % 2 == 0:\n",
    "                return 0\n",
    "\n",
    "            return move(-1, dis, k - 1) + move(1, dis, k - 1)\n",
    "        \n",
    "        return move(0, endPos - startPos, k) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        #dp = [[0 for _ in range(k+1)] for _ in range(endPos+1)]\n",
    "        dp = defaultdict(int)\n",
    "        dp[startPos,0] = 1\n",
    "        for i in range(1, k+1):\n",
    "            for j in range(startPos-k-1, startPos+k+2):\n",
    "                dp[j,i] = (dp[j-1,i-1] + dp[j+1,i-1]) % (10**9+7)\n",
    "        return dp[endPos,k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(maxsize=None)\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if k == 0 and startPos == endPos:\n",
    "            return 1 \n",
    "        if k<0:\n",
    "            return 0 \n",
    "        if abs(startPos-endPos)>k:\n",
    "            return 0 \n",
    "        return (self.numberOfWays(startPos-1, endPos, k-1) + self.numberOfWays(startPos+1, endPos, k-1)) % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def numberOfWays(self, s: int, e: int, k: int) -> int:\n",
    "        m = 10**9+7\n",
    "        if abs(s-e)>k:\n",
    "            return 0\n",
    "        if abs(s-e)==k:\n",
    "            return 1\n",
    "        return (self.numberOfWays(s,e-1,k-1)+self.numberOfWays(s,e+1,k-1))%m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        @ cache\n",
    "        def dfs(x,l):\n",
    "            if abs(endPos-x) > l:\n",
    "                return 0\n",
    "            if l == 0:\n",
    "                return 1\n",
    "            return dfs(x-1,l-1)+dfs(x+1,l-1)\n",
    "        return dfs(startPos,k)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:    \n",
    "        @cache\n",
    "        def f(s,e,kk):\n",
    "            d=abs(s-e)\n",
    "            if d>kk:\n",
    "                return 0\n",
    "            # if d&1 !=kk&1:\n",
    "            #     return 0\n",
    "            if kk==0:\n",
    "                if s==e:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            return f(s-1,e,kk-1)+f(s+1,e,kk-1)\n",
    "        return f(startPos,endPos,k)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        dp = [[0 for _ in range(3001)] for _ in range(k + 1)]\n",
    "        startPos += 1000\n",
    "        endPos += 1000\n",
    "        res = 0 \n",
    "        @lru_cache(None)\n",
    "        def helper(startPos, k):\n",
    "            nonlocal res\n",
    "            if abs(startPos - endPos) == 1 and k == 1:\n",
    "                # print(k, startPos)\n",
    "                dp[k][startPos] += 1\n",
    "            elif k < 1:\n",
    "                return 0\n",
    "            else:\n",
    "                helper(startPos - 1, k - 1)\n",
    "                helper(startPos + 1, k - 1)\n",
    "                dp[k][startPos] = (dp[k-1][startPos - 1] + dp[k-1][startPos + 1])%(10**9+7)\n",
    "        helper(startPos, k)\n",
    "        return dp[k][startPos]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if (endPos-startPos)>k or (endPos-startPos)&1 !=(k&1):\n",
    "            return 0\n",
    "        \n",
    "        MOD=10**9+7\n",
    "        @cache\n",
    "        def dfs(s,k):\n",
    "            if (endPos-s)>k :\n",
    "                return 0\n",
    "            if  k==0:\n",
    "                return 1 if s==endPos else 0\n",
    "            return dfs(s-1,k-1)%MOD+dfs(s+1,k-1)%MOD\n",
    "            \n",
    "        return dfs(startPos,k)%MOD\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        d = abs(startPos - endPos)\n",
    "        @cache\n",
    "        def get(x,l):\n",
    "            if x > l or l < 0:\n",
    "                return 0\n",
    "            if l == 0 and x == 0:\n",
    "                return 1\n",
    "            return (get(x+1, l-1) + get(x-1, l-1)) % MOD\n",
    "        return get(d,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def dp(ii, kk):\n",
    "            if abs(endPos - ii) > kk:\n",
    "                return 0\n",
    "            if abs(endPos - ii) == kk:\n",
    "                return 1\n",
    "\n",
    "            return (dp(ii-1, kk-1) + dp(ii+1, kk-1)) % 1000000007\n",
    "\n",
    "\n",
    "        return dp(startPos, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        # hash 存储记忆化的中间结果\n",
    "        memo = defaultdict(int)\n",
    "        # cur 3  d = 2   k =  3  end 6\n",
    "        # 记忆化搜索\n",
    "        # 当前距离为cur 已经走了d步 的方案数\n",
    "        # 写python 记忆化搜索一定要加个@cache 不然就会超时\n",
    "        @cache\n",
    "        def dfs(cur: int, d: int) -> int:\n",
    "            if k - d  < abs(endPos - cur):\n",
    "                return 0\n",
    "            if d == k:\n",
    "                return 1\n",
    "            # 这个key的赋值 是整个记忆化里最关键的一步\n",
    "            # key包含cur 以及 d 两个信息\n",
    "            # 如果只是从0开始 这两个信息可能会其冲突 比如 你cur = 3 可能只是向右了3步 但也可能是向右6步后折返了3步 即会产生哈希冲突\n",
    "            # 由于题目条件是最多走1000步 所以只要cur* 比1000大的数 不同的key之间就不会存在冲突了 \n",
    "            key = cur * 1005 + d\n",
    "            # 已经搜索过直接返回\n",
    "            if memo.get(key):\n",
    "                return memo[key]\n",
    "            v = (dfs(cur + 1, d + 1) + dfs(cur - 1, d + 1)) % MOD\n",
    "            memo[key] = v\n",
    "            return v\n",
    "\n",
    "        return dfs(startPos, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dp(pos, k):\n",
    "            if k<0:\n",
    "                return 0\n",
    "            if abs(pos-startPos) == k:\n",
    "                return 1\n",
    "            \n",
    "            return dp(pos+1, k-1)+dp(pos-1, k-1)\n",
    "        \n",
    "        return dp(endPos, k)%1000000007\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, sp: int, ep: int, k: int) -> int:\n",
    "        dis = ep - sp\n",
    "        mod = 10 ** 9 + 7\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(d, k):\n",
    "            if d == k:\n",
    "                return 1\n",
    "            if k <= 0:\n",
    "                return 0\n",
    "            ans = dp(d+1, k-1) + dp(d-1, k-1)\n",
    "            return ans % mod\n",
    "        \n",
    "        return dp(abs(dis), k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: int, e: int, k: int) -> int:\n",
    "        if abs(s-e) > k:\n",
    "            return 0\n",
    "        elif (e-s + k) & 1:\n",
    "            return 0\n",
    "        elif abs(s-e) == k:\n",
    "            return 1\n",
    "        else:\n",
    "            @functools.lru_cache(None)\n",
    "            def dfs(n, k):\n",
    "                if k == 0: return n == 0\n",
    "                return (dfs(n-1, k-1) + dfs(n+1, k-1)) % (10**9+7)\n",
    "            return dfs(e-s, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: int, e: int, k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dis = s - e if s >=e else e - s\n",
    "        if (k < dis) or (k - dis) % 2 == 1:\n",
    "            return 0\n",
    "        @cache\n",
    "        def dfs(c: int, p: int, k: int) -> int:\n",
    "            if(k < abs(c-e)):\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                return int(c == e)\n",
    "            ans = 0\n",
    "            ans += dfs(c-1, c, k-1)\n",
    "            ans %= mod\n",
    "            ans += dfs(c+1, c, k-1)  \n",
    "            ans %= mod\n",
    "            return ans\n",
    "        res = dfs(s,s - k,k)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        s = startPos\n",
    "        e = endPos\n",
    "        d = e-s \n",
    "        if k < d:\n",
    "            return 0\n",
    "        elif (k-d) % 2 == 1:\n",
    "            return 0\n",
    "        p = (k-d)//2 # 可以有 p 次的折返\n",
    "\n",
    "        l = s-p\n",
    "        r = e+p\n",
    "        # print(l, r)\n",
    "        '''\n",
    "        l l+1 l+2 ... s-1 s s+1 s+2 ... e-1 e e+1 ... r-1 r\n",
    "                          ^                 ^\n",
    "        0 1 2 3\n",
    "          - - -\n",
    "        '''\n",
    "        ## dp\n",
    "        cache = {}\n",
    "        def dp(i=s, k=k):\n",
    "            if (i, k) in cache:\n",
    "                return cache[(i, k)]\n",
    "            if k == 0:\n",
    "                if i == e:\n",
    "                    return 1 \n",
    "                return 0\n",
    "            elif k < 0:\n",
    "                return 0\n",
    "            if i == l:\n",
    "                res = dp(i+1, k-1)\n",
    "            elif i == r:\n",
    "                res = dp(i-1, k-1)\n",
    "            else:\n",
    "                res = dp(i+1, k-1) + dp(i-1, k-1)\n",
    "            cache[(i, k)] = res\n",
    "            return res \n",
    "\n",
    "        res = dp(s, k)\n",
    "        res = int(res%1000000007)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int, MOD = 10**9 + 7) -> int:\n",
    "        @cache\n",
    "        def dfs(n, k):\n",
    "            if n > k: return 0\n",
    "            if k == 0: return n == 0\n",
    "            return (dfs(n + 1, k - 1) + dfs(n - 1, k - 1)) % MOD\n",
    "        return dfs(endPos - startPos, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def f(i, j, k):\n",
    "            if j-i > k:\n",
    "                return 0\n",
    "            if j-i == k:\n",
    "                return 1\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            return (f(i-1, j, k-1)+f(i+1, j, k-1))%MOD\n",
    "        return f(startPos, endPos, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if (k - (endPos - startPos)) % 2 != 0 or (k - (endPos - startPos)) < 0: return 0\n",
    "        if k == endPos - startPos: return 1\n",
    "        @lru_cache(None)\n",
    "        def dfs(pos, step):\n",
    "            if pos == endPos and step == 0: return 1\n",
    "            if step == 0: return 0\n",
    "            return dfs(pos + 1, step - 1) + dfs(pos - 1, step - 1)\n",
    "        return dfs(startPos, k) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        e = abs(startPos - endPos)\n",
    "        if e > k or (k - e) & 1:\n",
    "            return 0\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def f(k: int, p: int) -> int:\n",
    "            '''位置 p, 剩余步数 k'''\n",
    "            if k < 0:\n",
    "                return 0\n",
    "            if k == 0 and p == 0:\n",
    "                return 1\n",
    "            return (f(k - 1, p - 1) + f(k - 1, p + 1)) % mod\n",
    "\n",
    "        return f(k, e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: int, e: int, k: int) -> int:\n",
    "        if abs(s-e) > k:\n",
    "            return 0\n",
    "        elif (e-s + k) & 1:\n",
    "            return 0\n",
    "        else:\n",
    "            @functools.lru_cache(None)\n",
    "            def dfs(n, k):\n",
    "                if k == 0: return n == 0\n",
    "                return (dfs(n-1, k-1) + dfs(n+1, k-1)) % (10**9+7)\n",
    "            return dfs(e-s, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: int, e: int, k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        @cache\n",
    "        def dfs(cur, rem):\n",
    "            if rem > k : return 0\n",
    "            if cur == e and rem == k: return 1\n",
    "            if cur + k - rem < e: return 0\n",
    "            return (dfs(cur - 1, rem + 1) + dfs(cur + 1, rem + 1)) % mod\n",
    "        \n",
    "        return dfs(s, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        # dfs\n",
    "        # 枚举向左/向右挪动相应的步数，到达某个位置的方法数\n",
    "        @cache\n",
    "        def dfs(cur_pos, step, k, endPos):\n",
    "            if step == k:\n",
    "                if cur_pos == endPos:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            \n",
    "            # 剪枝 - 跳k步跳不到终点，及时返回\n",
    "            if abs(endPos-cur_pos) > k:\n",
    "                return 0\n",
    "\n",
    "            # 向左挪动一步\n",
    "            l_methods = dfs(cur_pos-1, step+1, k, endPos)\n",
    "            l_methods = l_methods % self.MOD\n",
    "            # 向右挪动一步\n",
    "            r_methods = dfs(cur_pos+1, step+1, k, endPos)\n",
    "            r_methods = r_methods % self.MOD\n",
    "            return (l_methods + r_methods) % self.MOD\n",
    "\n",
    "\n",
    "        # 排除一些肯定不满足条件的case\n",
    "        if k % 2 == 0:\n",
    "            if startPos % 2 != endPos % 2:\n",
    "                return 0\n",
    "        else:\n",
    "            if startPos % 2 == endPos % 2:\n",
    "                return 0\n",
    "        self.MOD = 10 ** 9 + 7\n",
    "        return dfs(startPos, 0, k, endPos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        dis = endPos - startPos\n",
    "        if dis > k:\n",
    "            return 0\n",
    "        if dis == k:\n",
    "            return 1\n",
    "        @cache\n",
    "        def dfs(cur: int, kk: int) -> int:\n",
    "            if endPos - cur > kk:\n",
    "                return 0\n",
    "            elif endPos - cur == kk:\n",
    "                return 1\n",
    "            elif kk == 0:\n",
    "                return 0\n",
    "            return dfs(cur - 1, kk - 1) + dfs(cur + 1, kk - 1)\n",
    "        return dfs(startPos, k) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if abs(startPos-endPos-k)%2:return 0\n",
    "        @cache\n",
    "        def helper(dist,n):\n",
    "            if n==0:return 1 if dist==0 else 0\n",
    "            return helper(dist-1,n-1)+helper(dist+1,n-1)\n",
    "        return helper(abs(endPos-startPos),k)%int(10**9+7)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        \n",
    "        @cache\n",
    "        def dfs(cur, rest):\n",
    "            if abs(cur - endPos) > k:\n",
    "                return 0\n",
    "            if rest < 0:\n",
    "                return 0\n",
    "            if rest == 0:\n",
    "                return 1 if cur == endPos else 0\n",
    "            else:\n",
    "                res = 0\n",
    "\n",
    "                # 向左向右分别枚举\n",
    "                res += dfs(cur + 1, rest - 1)\n",
    "                res += dfs(cur - 1, rest - 1)\n",
    "                return res % mod\n",
    "        \n",
    "        return dfs(startPos, k) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        from functools import cache\n",
    "        MOD = 1000000000 + 7\n",
    "        @cache\n",
    "        def recur(pos, k):\n",
    "            if abs(pos - startPos) > 1010:\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                if pos == startPos:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                return (recur(pos - 1, k - 1) + recur(pos + 1, k - 1)) % MOD\n",
    "        return recur(endPos, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if abs(startPos - endPos) == k:\n",
    "            return 1\n",
    "        \n",
    "        if abs(startPos - endPos) > k:\n",
    "            return 0\n",
    "        \n",
    "        \n",
    "        @cache\n",
    "        def dfs(pos, steps):\n",
    "            if steps == k:\n",
    "                if pos == endPos:\n",
    "                    return 1\n",
    "                return 0\n",
    "            \n",
    "            return (dfs(pos + 1, steps + 1) + dfs(pos - 1, steps + 1)) % 1000000007\n",
    "        \n",
    "        return dfs(startPos, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(start, end, k):\n",
    "    if k == 0 and end == start:\n",
    "        return 1\n",
    "    elif k == 0 and end != start:\n",
    "        return 0\n",
    "\n",
    "    # print(dfs(start, end - 1, k - 1) , dfs(start, end - 1, k - 1))\n",
    "    return (dfs(start, end - 1, k - 1) + dfs(start, end + 1, k - 1)) % (1000000007)\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "\n",
    "        return dfs(startPos, endPos, k)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        if startPos < endPos - k or startPos > endPos + k :\n",
    "            return 0 \n",
    "        \n",
    "        memo = {}\n",
    "        def dfs(index, move):\n",
    "            if (index, move) in memo:\n",
    "                return memo[(index, move)]\n",
    "            if move > k:\n",
    "                return 0\n",
    "            if move == k:\n",
    "                if index == endPos:\n",
    "                    return 1\n",
    "                return 0 \n",
    "            val = 0 \n",
    "            if index + 1 <= endPos + k and index + 1 >= endPos - k :\n",
    "                val += dfs(index+1, move + 1)\n",
    "            if index - 1 <= endPos + k and index - 1 >= endPos - k :\n",
    "                val += dfs(index-1, move + 1)\n",
    "            memo[(index, move)] = val % mod\n",
    "            return memo[(index, move)]  \n",
    "        ans = dfs(startPos, 0)\n",
    "        return ans % mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    @cache\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if k < 0:\n",
    "            return 0\n",
    "\n",
    "        if endPos - startPos == k:\n",
    "            return 1\n",
    "        elif endPos - startPos > k:\n",
    "            return 0\n",
    "        else:\n",
    "            return (self.numberOfWays(startPos + 1, endPos, k - 1) + self.numberOfWays(startPos - 1, endPos, k - 1))%int(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, start: int, end: int, k: int) -> int:\n",
    "        if start>end:\n",
    "            start,end=end,start\n",
    "            \n",
    "        mod=10**9+7\n",
    "        \n",
    "        \n",
    "        @cache\n",
    "        def dfs(pos,left):\n",
    "            if left==0:\n",
    "                return int(pos==end)\n",
    "            \n",
    "            ans=0\n",
    "            # if abs(end-pos)>left:return 0\n",
    "            ans+=dfs(pos+1,left-1)\n",
    "            ans+=dfs(pos-1,left-1)\n",
    "            return ans%mod\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        return dfs(start,k)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "        a, b, c, d = 1, 0, 0, 0\n",
    "        for i in range(k):  a, b, c, d = ((m-1)*b+(n-1)*c) % 1000000007, (a+(m-2)*b+(n-1)*d) % 1000000007, (a+(n-2)*c+(m-1)*d) % 1000000007, (b+c+(m+n-4)*d) % 1000000007\n",
    "        if source[0] == dest[0]: return a if source[1] == dest[1] else b\n",
    "        else: return c if source[1] == dest[1] else d\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        f = [1, 0, 0, 0]\n",
    "        for _ in range(k):\n",
    "            g = [0] * 4\n",
    "            g[0] = ((n - 1) * f[1] + (m - 1) * f[2]) % mod\n",
    "            g[1] = (f[0] + (n - 2) * f[1] + (m - 1) * f[3]) % mod\n",
    "            g[2] = (f[0] + (m - 2) * f[2] + (n - 1) * f[3]) % mod\n",
    "            g[3] = (f[1] + f[2] + (n - 2) * f[3] + (m - 2) * f[3]) % mod\n",
    "            f = g\n",
    "        if source[0] == dest[0]:\n",
    "            return f[0] if source[1] == dest[1] else f[2]\n",
    "        return f[1] if source[1] == dest[1] else f[3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "        dp = [0] * 4\n",
    "        if source[0] == dest[0] and source[1] == dest[1]:\n",
    "            dp[3] = 1\n",
    "        elif source[1] == dest[1]:\n",
    "            dp[2] = 1\n",
    "        elif source[0] == dest[0]:\n",
    "            dp[1] = 1\n",
    "        else:\n",
    "            dp[0] = 1\n",
    "        for _ in range(k):\n",
    "            dp = [\n",
    "                (dp[0] * (n + m - 4) + dp[1] * (n - 1) + dp[2] * (m - 1)) % MOD,\n",
    "                (dp[0] + dp[1] * (m - 2) + dp[3] * (m - 1)) % MOD,\n",
    "                (dp[0] + dp[2] * (n - 2) + dp[3] * (n - 1)) % MOD,\n",
    "                (dp[1] + dp[2]) % MOD\n",
    "            ]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        a, b, c, d = 1, 0, 0, 0\n",
    "        for _ in range(k):\n",
    "            aa = ((n - 1) * b + (m - 1) * c) % mod\n",
    "            bb = (a + (n - 2) * b + (m - 1) * d) % mod\n",
    "            cc = (a + (m - 2) * c + (n - 1) * d) % mod\n",
    "            dd = (b + c + (n - 2) * d + (m - 2) * d) % mod\n",
    "            a, b, c, d = aa, bb, cc, dd\n",
    "        if source[0] == dest[0]:\n",
    "            return a if source[1] == dest[1] else c\n",
    "        return b if source[1] == dest[1] else d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "\n",
    "        mod = 10**9+7\n",
    "        dp = [0,0,0,0]\n",
    "        dp[(source[1]==dest[1])*2+(source[0]==dest[0])]=1\n",
    "\n",
    "        for p in range(1,k+1):\n",
    "            dp1 = [0,0,0,0]\n",
    "            dp1[0] = (dp[0]*(n+m-4)+dp[1]*(n-1)+dp[2]*(m-1))%mod\n",
    "            dp1[1] = (dp[0]+dp[1]*(m-2)+dp[3]*(m-1))%mod\n",
    "            dp1[2] = (dp[0]+dp[2]*(n-2)+dp[3]*(n-1))%mod\n",
    "            dp1[3] = (dp[1]+dp[2])%mod\n",
    "            dp = dp1\n",
    "\n",
    "        return dp[-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "\n",
    "        mod = 10**9+7\n",
    "        dp = [0,0,0,0]\n",
    "        dp[(source[1]==dest[1])*2+(source[0]==dest[0])]=1 # 设边界条件\n",
    "        \n",
    "        for p in range(1,k+1):\n",
    "            dp1 = [0,0,0,0] # 需要辅助数组，在一轮全部更新完之前不允许覆盖\n",
    "            dp1[0] = (dp[0]*(n+m-4)+dp[1]*(n-1)+dp[2]*(m-1))%mod\n",
    "            dp1[1] = (dp[0]+dp[1]*(m-2)+dp[3]*(m-1))%mod\n",
    "            dp1[2] = (dp[0]+dp[2]*(n-2)+dp[3]*(n-1))%mod\n",
    "            dp1[3] = (dp[1]+dp[2])%mod\n",
    "            dp = dp1\n",
    "\n",
    "        return dp[3] # 最终要的当然是x和y都正确"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "        f = [0] * 4\n",
    "        f[(source[0] == dest[0]) + (source[1] == dest[1]) * 2] = 1\n",
    "        for _ in range(k):\n",
    "            a, b, c, d = f\n",
    "            f[0] = b * (n - 1) + c * (m - 1) + a * (m - 2) + a * (n - 2)\n",
    "            f[1] = a + d * (m - 1) + b * (m - 2)\n",
    "            f[2] = a + d * (n - 1) + c * (n - 2)\n",
    "            f[3] = b + c\n",
    "            f = [x % MOD for x in f]\n",
    "        return f[3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "        a, b, c, d = 1, 0, 0, 0\n",
    "        for i in range(k):  a, b, c, d = ((m-1)*b+(n-1)*c) % 1000000007, (a+(m-2)*b+(n-1)*d) % 1000000007, (a+(n-2)*c+(m-1)*d) % 1000000007, (b+c+(m+n-4)*d) % 1000000007\n",
    "        if source[0] == dest[0]: return a if source[1] == dest[1] else b\n",
    "        else: return c if source[1] == dest[1] else d\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        a,b,c,d = 0,0,0,0\n",
    "        if source==dest: a = 1\n",
    "        elif source[0] == dest[0]: b = 1\n",
    "        elif source[1]==dest[1]: c = 1\n",
    "        else: d = 1\n",
    "        for _ in range(k):\n",
    "            a2 = b+c\n",
    "            b2 = a*(m-1)+b*(m-2)+d\n",
    "            c2 = a*(n-1)+c*(n-2)+d\n",
    "            d2 = b*(n-1)+c*(m-1)+d*(n-2)+d*(m-2)\n",
    "            a,b,c,d = a2%mod,b2%mod,c2%mod,d2%mod\n",
    "        return a\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "\n",
    "        s1,s2 = source\n",
    "        d1,d2 = dest\n",
    "        MODX = 10**9+7\n",
    "\n",
    "        dp = [0,0,0,0]\n",
    "        dp[(s2==d2)*2+(s1==d1)] = 1\n",
    "        print(dp)\n",
    "\n",
    "        for i in range(1,k+1):\n",
    "            dp1 = [0,0,0,0]\n",
    "            dp1[0] = dp[0]*(n+m-4)+dp[1]*(n-1)+dp[2]*(m-1)\n",
    "            dp1[1] = dp[0]+dp[1]*(m-2)+dp[3]*(m-1)\n",
    "            dp1[2] = dp[0]*1+dp[2]*(n-2)+dp[3]*(n-1)\n",
    "            dp1[3] = dp[1]+dp[2]\n",
    "\n",
    "            for j in range(4):\n",
    "                dp1[j] %= MODX\n",
    "            dp = dp1[:]\n",
    "        \n",
    "        return dp[3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10**9 + 7\n",
    "def fix(a, b):\n",
    "    n = len(a) \n",
    "    m = len(b[0])\n",
    "    p = len(a[0])\n",
    "    c = [[0]*m for _ in range(n)]\n",
    "    for i in range(n):\n",
    "        for j in range(m):\n",
    "            t = 0\n",
    "            for k in range(p):\n",
    "                t += a[i][k]*b[k][j]\n",
    "            c[i][j] = (t%mod)\n",
    "    return c \n",
    "\n",
    "\n",
    "def qM(a, j):\n",
    "    n = len(a)\n",
    "    ans = [[0]*n for _ in range(n)]\n",
    "    for i in range(n):\n",
    "        ans[i][i] = 1 \n",
    "    if j==0: \n",
    "        return ans \n",
    "    else:\n",
    "        s = bin(j)[2:][::-1]\n",
    "        st = a \n",
    "        for i in s:\n",
    "            if i=='1':\n",
    "                ans = fix(ans, st)\n",
    "            st = fix(st, st) \n",
    "        return ans \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, s: List[int], d: List[int]) -> int:\n",
    "        a = [[0, 0, 0, 0]]\n",
    "        if s==d:\n",
    "            a[0][0] = 1\n",
    "        elif s[0]==d[0]:\n",
    "            a[0][1] = 1 \n",
    "        elif s[1]==d[1]:\n",
    "            a[0][2] = 1 \n",
    "        else:\n",
    "            a[0][3] = 1 \n",
    "        b = [[0,m-1,n-1,0], [1,m-2,0,n-1], [1,0,n-2,m-1], [0,1,1,n-2+m-2]]\n",
    "        ans = fix(a, qM(b, k))[0]\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "\n",
    "        mod = 10**9+7\n",
    "        dp = [0,0,0,0]\n",
    "\n",
    "        if source[0]==dest[0] and source[1]==dest[1]:\n",
    "            dp[3]+=1\n",
    "        elif source[0]==dest[0]:\n",
    "            dp[1]+=1\n",
    "        elif source[1]==dest[1]:\n",
    "            dp[2]+=1\n",
    "        else:\n",
    "            dp[0]=1\n",
    "        \n",
    "        print(dp)\n",
    "        for p in range(1,k+1):\n",
    "            dp1 = [0,0,0,0]\n",
    "            dp1[0] = (dp[0]*(n+m-4)+dp[1]*(n-1)+dp[2]*(m-1))%mod\n",
    "            dp1[1] = (dp[0]+dp[1]*(m-2)+dp[3]*(m-1))%mod\n",
    "            dp1[2] = (dp[0]+dp[2]*(n-2)+dp[3]*(n-1))%mod\n",
    "            dp1[3] = (dp[1]+dp[2])%mod\n",
    "            dp = dp1\n",
    "\n",
    "        return dp[-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "class Combi:\n",
    "    __slots__ = ('f', 'g')\n",
    "\n",
    "    def __init__(self, n: int) -> None:\n",
    "        assert (n < MOD)\n",
    "        self.f = [1] * (n + 1)\n",
    "        self.g = [1] * (n + 1)\n",
    "        for i in range(2, n + 1): self.f[i] = self.f[i - 1] * i % MOD\n",
    "        self.g[n] = pow(self.f[n], MOD - 2, MOD)\n",
    "        for i in range(n, 1, -1): self.g[i - 1] = self.g[i] * i % MOD\n",
    "\n",
    "    def choose(self, n: int, r: int) -> int:\n",
    "        if r < 0 or r > n: return 0\n",
    "        return (self.f[n] * self.g[n - r] % MOD) * self.g[r] % MOD\n",
    "\n",
    "    def multichoose(self, u: int, k: int) -> int:\n",
    "        if k < 0 or k > (u + k - 1): return 0\n",
    "        return (self.f[u + k - 1] * self.g[u - 1] % MOD) * self.g[k] % MOD\n",
    "\n",
    "    def permutation(self, n: int, r: int) -> int:\n",
    "        if r < 0 or r > n: return 0\n",
    "        return self.f[n] * self.g[n - r] % MOD\n",
    "\n",
    "    def catalan(self, n):\n",
    "        return (self.choose(2 * n, n) - self.choose(2 * n, n - 1)) % self.MOD\n",
    "\n",
    "    def inv(self, n):\n",
    "        return self.f[n - 1] * self.g[n] % MOD\n",
    "\n",
    "cnk = Combi(100000).choose\n",
    "\n",
    "Matrix = List[List[int]]\n",
    "\n",
    "def MatrixMul(mat1: Matrix, mat2: Matrix) -> Matrix:\n",
    "    return [[sum(mat1[i][k] * mat2[k][j]\n",
    "                 for k in range(2)) % MOD\n",
    "             for j in range(2)]\n",
    "            for i in range(2)]\n",
    "\n",
    "def gao(base: Matrix, t: int, idx: int):\n",
    "    cur = deepcopy(base)\n",
    "    res = [1 - idx]\n",
    "    for _ in range(t):\n",
    "        res.append(cur[0][idx])\n",
    "        cur = MatrixMul(cur, base)\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "        dx, dy = dest[0] - source[0], dest[1] - source[1]\n",
    "        res = 0\n",
    "\n",
    "        # baseN, baseM = [[0, 1], [n - 1, n - 2]], [[0, 1], [m - 1, m - 2]]\n",
    "        # matN, matM = MatrixPow([[0, 1], [n - 1, n - 2]]), MatrixPow([[0, 1], [m - 1, m - 2]])\n",
    "\n",
    "        # def countN(t: int):\n",
    "        #     res = matN.trans([[1, 0]], t)\n",
    "        #     return res[0][dx != 0]\n",
    "        # def countM(t: int):\n",
    "        #     res = matM.trans([[1, 0]], t)\n",
    "        #     return res[0][dy != 0]\n",
    "\n",
    "        N = gao([[0, 1], [n - 1, n - 2]], k, dx != 0)\n",
    "        M = gao([[0, 1], [m - 1, m - 2]], k, dy != 0)\n",
    "\n",
    "        for a in range(k + 1):\n",
    "            b = k - a\n",
    "            # res += countN(a) * countM(b) * cnk(k, a) % MOD\n",
    "            res += N[a] * M[b] * cnk(k, a) % MOD\n",
    "            res %= MOD\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "import numpy as np \n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "        mat = np.array([[n+m-4,n-1,m-1,0],[1,m-2,0,m-1],[1,0,n-2,n-1],[0,1,1,0]])\n",
    "        sx, sy = source\n",
    "        dx, dy = dest\n",
    "        dp = [sx!=dx and sy!=dy, sx==dx and sy!=dy, sx!=dx and sy==dy, sx==dx and sy==dy]\n",
    "        dp = np.array(dp,dtype=int)\n",
    "        # ans = np.eye(4,4)\n",
    "        ans = dp \n",
    "        cur = mat \n",
    "        while k:\n",
    "            if k&1:\n",
    "                ans = cur@ans \n",
    "                ans %= MOD \n",
    "            cur = cur@cur \n",
    "            cur %= MOD\n",
    "            k >>= 1\n",
    "        # for _ in range(k):\n",
    "        #     dp = mat@dp\n",
    "        #     dp %= MOD\n",
    "        # dp = (ans@dp)%MOD\n",
    "        return int(ans[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "import numpy as np \n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "        mat = np.array([[n+m-4,n-1,m-1,0],[1,m-2,0,m-1],[1,0,n-2,n-1],[0,1,1,0]])\n",
    "        sx, sy = source\n",
    "        dx, dy = dest\n",
    "        dp = [sx!=dx and sy!=dy, sx==dx and sy!=dy, sx!=dx and sy==dy, sx==dx and sy==dy]\n",
    "        dp = np.array(dp,dtype=int)\n",
    "        ans = np.eye(4,4,dtype=int)\n",
    "        # ans = dp \n",
    "        cur = mat \n",
    "        while k:\n",
    "            if k&1:\n",
    "                ans = cur@ans \n",
    "                ans %= MOD \n",
    "            cur = cur@cur \n",
    "            cur %= MOD\n",
    "            k >>= 1\n",
    "        # for _ in range(k):\n",
    "        #     dp = mat@dp\n",
    "        #     dp %= MOD\n",
    "        dp = (ans@dp)%MOD\n",
    "        return int(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "dtype = np.dtype('uint64')\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:\n",
    "        f = [0] * 4\n",
    "        f[(source[0] == dest[0]) + (source[1] == dest[1]) * 2] = 1\n",
    "        mul = np.array([\n",
    "            [n + m - 4, n - 1, m - 1, 0],\n",
    "            [1, m - 2, 0, m - 1],\n",
    "            [1, 0, n - 2, n - 1],\n",
    "            [0, 1, 1, 0]\n",
    "        ], dtype=dtype)\n",
    "        mat = np.eye(4, dtype=dtype)\n",
    "        while k:\n",
    "            if k & 1: mat = mul @ mat % MOD\n",
    "            k >>= 1\n",
    "            mul = mul @ mul % MOD\n",
    "        return int((mat @ np.array(f, dtype=dtype))[3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        zeros=(s[0]==\"0\")+(s[1]==\"0\")\n",
    "        ones=(s[0]==\"1\")+(s[1]==\"1\")\n",
    "        onezeros=1 if s[:2]==\"10\" else 0\n",
    "        zeroones=1 if s[:2]==\"01\" else 0\n",
    "        nw=0\n",
    "        for c in s[2:]:\n",
    "            #print(zeros, ones, onezeros, zeroones,nw)\n",
    "            if c==\"1\":\n",
    "                nw+=onezeros\n",
    "                zeroones+=zeros\n",
    "            else:\n",
    "                nw+=zeroones\n",
    "                onezeros+=ones\n",
    "            zeros+=c==\"0\"\n",
    "            ones+=c==\"1\"\n",
    "        return nw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        zeros = s.count('0')\n",
    "        ones = len(s) - zeros\n",
    "        z = o = 0\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                ans += z*zeros\n",
    "                ones -= 1\n",
    "                o += 1\n",
    "            else:\n",
    "                ans += o*ones\n",
    "                z += 1\n",
    "                zeros -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        tot0 = s.count(\"0\")\n",
    "        ans = c0 = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == \"1\":\n",
    "                ans += c0 * (tot0 - c0)\n",
    "            else:\n",
    "                ans += (i - c0) * (len(s) - tot0 - i + c0)\n",
    "                c0 += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numberOfWays(self, s: str) -> int:\r\n",
    "        zero = s.count('0')\r\n",
    "        one = s.count('1')\r\n",
    "        before_zero = 0\r\n",
    "        before_one = 0\r\n",
    "        ans = 0\r\n",
    "        n = len(s)\r\n",
    "        for i, c in enumerate(s):\r\n",
    "            if c == '0':\r\n",
    "                zero -= 1\r\n",
    "                before_zero += 1\r\n",
    "                ans += before_one * one if 0 < i < n - 1 else 0\r\n",
    "            else:\r\n",
    "                one -= 1\r\n",
    "                before_one += 1\r\n",
    "                ans += before_zero * zero if 0 < i < n - 1 else 0\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        tot = s.count('1')\n",
    "        res = 0\n",
    "        cur0 = 0\n",
    "        cur1 = 0\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] == '1':\n",
    "                res += cur0 * (n - cur0 - tot)\n",
    "                cur1 += 1\n",
    "            else:\n",
    "                res += cur1 * (tot - cur1)\n",
    "                cur0 += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        n1 = s.count('1')   # s 中 '1' 的个数\n",
    "        res = 0   # 两种子序列的个数总和\n",
    "        cnt = 0   # 遍历到目前为止 '1' 的个数\n",
    "        for i in range(n):\n",
    "            if s[i] == '1':\n",
    "                res += (i - cnt) * (n - n1 - i + cnt)\n",
    "                cnt += 1\n",
    "            else:\n",
    "                res += cnt * (n1 - cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        \n",
    "        n = len(s)\n",
    "        n0 = s.count('0')   # 0的总数目\n",
    "        n1 = n-n0           # 1的总数目\n",
    "\n",
    "        cnt0 = 0            # 左起0的数目\n",
    "        cnt1 = 0            # 左起1的数目\n",
    "        ans = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '0':\n",
    "                cnt0 += 1\n",
    "                ans += cnt1 * (n1-cnt1)     # 左边1的数目 * 右边1的数目\n",
    "            else:\n",
    "                cnt1 += 1\n",
    "                ans += cnt0 * (n0-cnt0)     # 左边0的数目 * 右边0的数目\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        zeros=(s[0]==\"0\")+(s[1]==\"0\")\n",
    "        ones=(s[0]==\"1\")+(s[1]==\"1\")\n",
    "        onezeros=1 if s[:2]==\"10\" else 0\n",
    "        zeroones=1 if s[:2]==\"01\" else 0\n",
    "        nw=0\n",
    "        for c in s[2:]:\n",
    "            #print(zeros, ones, onezeros, zeroones,nw)\n",
    "            if c==\"1\":\n",
    "                nw+=onezeros\n",
    "                zeroones+=zeros\n",
    "            else:\n",
    "                nw+=zeroones\n",
    "                onezeros+=ones\n",
    "            zeros+=(c==\"0\")\n",
    "            ones+=(c==\"1\")\n",
    "        return nw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        zero = s.count('0')\n",
    "        one = n - zero\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        for i,x in enumerate(s):\n",
    "            if x == '0':\n",
    "                ans += (i - cnt)*(one - i + cnt)\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ans += cnt * (zero - cnt)\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        # 倒序遍历，记录1的数量和0的数量的后缀数量的后缀和\n",
    "        # 对于每个1，加上0的后缀和，对于每个0，加上1的后缀和\n",
    "        ans = c0 = c1 = 0\n",
    "        s0 = s1 = 0\n",
    "        for c in s[::-1]:\n",
    "            if c == '0':\n",
    "                c0 += 1\n",
    "                s0 += c1\n",
    "                ans += s1\n",
    "            else:\n",
    "                c1 += 1\n",
    "                s1 += c0\n",
    "                ans += s0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        # ans = 0\n",
    "        # path = []\n",
    "        # # @cache\n",
    "        # def dfs(i):\n",
    "        #     if len(path) == 3:\n",
    "        #         if (path[1] == '1' and path[0] == path[2] == '0') or (path[1] == '0' and path[0] == path[2] == '1'):\n",
    "        #             nonlocal ans \n",
    "        #             ans += 1\n",
    "        #         return\n",
    "        #     if i >= len(s) or len(path) > 3:\n",
    "        #         return\n",
    "\n",
    "        #     path.append(s[i])\n",
    "        #     dfs(i+1)\n",
    "        #     path.pop()\n",
    "        #     dfs(i+1)\n",
    "        # dfs(0)\n",
    "        # return ans\n",
    "\n",
    "        total_0 = s.count('0')\n",
    "        ans = 0\n",
    "        left_0 = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '1':\n",
    "                ans += left_0 * (total_0 - left_0)\n",
    "            else:\n",
    "                left_1 = i-left_0\n",
    "                ans += left_1 * (len(s) - total_0 - left_1)\n",
    "                left_0 += 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        zeros,ones=s.count('0'),s.count('1')\n",
    "        lz,lo=0,0\n",
    "        res=0\n",
    "        for i in s:\n",
    "            if i=='1':\n",
    "                ones-=1\n",
    "                lo+=1\n",
    "                res+=(zeros*lz) \n",
    "            if i=='0':\n",
    "                zeros-=1\n",
    "                lz+=1\n",
    "                res+=(ones*lo)\n",
    "        return res \n",
    "           \n",
    "           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        count=Counter(s)\n",
    "        s0=0\n",
    "        s1=0\n",
    "        if s[0]==\"0\":\n",
    "            s0+=1\n",
    "        else:\n",
    "            s1+=1\n",
    "        ans=0\n",
    "        for s in s[1:]:\n",
    "            if s==\"0\":\n",
    "                ans+=s1*(count[\"1\"]-s1)\n",
    "                s0+=1\n",
    "            else:\n",
    "                ans+=s0*(count[\"0\"]-s0)\n",
    "                s1+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        one_cnt = 0\n",
    "        zero_cnt = 0\n",
    "\n",
    "        for build in s:\n",
    "            if build == '1':\n",
    "                one_cnt += 1\n",
    "            else:\n",
    "                zero_cnt += 1\n",
    "\n",
    "        one_pre_cnt = 0\n",
    "        zero_pre_cnt = 0\n",
    "        ans = 0\n",
    "        for build in s:\n",
    "            if build == '1':\n",
    "                ans += zero_pre_cnt * (zero_cnt - zero_pre_cnt)\n",
    "                one_pre_cnt += 1\n",
    "            else:\n",
    "                ans += one_pre_cnt * (one_cnt - one_pre_cnt)\n",
    "                zero_pre_cnt += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        total0 = total1 = 0\n",
    "        count0 = count1 = 0\n",
    "        last0 = last1 = 0\n",
    "        lastRes0 = lastRes1 = 0\n",
    "        sLen = len(s)\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(sLen):\n",
    "            if s[i] == '0':\n",
    "                total0 += 1\n",
    "                if i > 0 and s[i] != s[i-1]:\n",
    "                    last1 = count1\n",
    "                    count1 = 0\n",
    "                count0 += 1\n",
    "\n",
    "            else:\n",
    "                total1 += 1\n",
    "                if i > 0 and s[i] != s[i-1]:\n",
    "                    last0 = count0\n",
    "                    count0 = 0\n",
    "                count1 += 1\n",
    "\n",
    "            \n",
    "            if i == sLen-1 or s[i] != s[i+1]:\n",
    "                if s[i] == '0' and last0 > 0:\n",
    "                    res = 0\n",
    "                    if lastRes0 == 0:\n",
    "                        res = last0*last1*count0\n",
    "                    else:\n",
    "                        tmp = lastRes0//last0\n",
    "                        res = tmp*count0\n",
    "                        res += (total0-count0)*last1*count0\n",
    "                    lastRes0 = res\n",
    "                    ans += lastRes0\n",
    "                elif s[i] == '1' and last1 > 0:\n",
    "                    res = 0\n",
    "                    if lastRes1 == 0:\n",
    "                        res = last1*last0*count1\n",
    "                    else:\n",
    "                        tmp = lastRes1//last1\n",
    "                        res = tmp*count1\n",
    "                        res += (total1-count1)*last0*count1\n",
    "                    lastRes1 = res\n",
    "                    ans += lastRes1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        n1 = s.count('1')\n",
    "        res = 0\n",
    "        cnt = 0 \n",
    "        for i in range(n):\n",
    "            if s[i] == '1':\n",
    "                res += (i - cnt) * (n - n1 - i + cnt)\n",
    "                cnt += 1\n",
    "            else:\n",
    "                res += cnt * (n1 - cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        zero = s.count('0')\n",
    "        one = len(s) - zero\n",
    "        ans = 0\n",
    "        left0 = 0  # 010 模式\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                left0 += 1\n",
    "            else:\n",
    "                ans += left0*(zero-left0)\n",
    "        left1 = 0  # 101 模式\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '1':\n",
    "                left1 += 1\n",
    "            else:\n",
    "                ans += left1*(one-left1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        \n",
    "        n = len(s)\n",
    "        n0 = s.count('0')   # 0的总数目\n",
    "        n1 = n-n0           # 1的总数目\n",
    "\n",
    "        cnt0 = 0            # 左起0的数目\n",
    "        cnt1 = 0            # 左起1的数目\n",
    "        ans = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '0':\n",
    "                cnt0 += 1\n",
    "                ans += cnt1 * (n1-cnt1)     # 左边1的数目 * 右边1的数目\n",
    "            else:\n",
    "                cnt1 += 1\n",
    "                ans += cnt0 * (n0-cnt0)     # 左边0的数目 * 右边0的数目\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numberOfWays(self, s: str) -> int:\r\n",
    "        zero = s.count('0')\r\n",
    "        one = s.count('1')\r\n",
    "        before_zero = 0\r\n",
    "        before_one = 0\r\n",
    "        ans = 0\r\n",
    "        for i, c in enumerate(s):\r\n",
    "            if c == '0':\r\n",
    "                zero -= 1\r\n",
    "                before_zero += 1\r\n",
    "            else:\r\n",
    "                one -= 1\r\n",
    "                before_one += 1\r\n",
    "            if 0 < i < len(s) - 1:\r\n",
    "                if c == '0':\r\n",
    "                    ans += before_one * one\r\n",
    "                else:\r\n",
    "                    ans += before_zero * zero\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        zeros = s.count('0')\n",
    "        ones = s.count('1')\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        zerosLeft = 0\n",
    "        onesLeft = 0\n",
    "\n",
    "        if s[0] == '0':\n",
    "            zerosLeft += 1\n",
    "        else:\n",
    "            onesLeft += 1\n",
    "\n",
    "        for i in range(1, len(s) - 1):\n",
    "            if s[i] == '0':\n",
    "                res += onesLeft * (ones - onesLeft)\n",
    "                zerosLeft += 1\n",
    "            else:\n",
    "                res += zerosLeft * (zeros - zerosLeft)\n",
    "                onesLeft += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        left = {\n",
    "            \"0\": 0,\n",
    "            \"1\": 0\n",
    "        }\n",
    "        right = Counter(s)\n",
    "        if len(right.keys()) <= 1:\n",
    "            return 0\n",
    "        left[s[0]] += 1\n",
    "        right[s[0]] -= 1\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == \"1\":\n",
    "                ans += left[\"0\"] * right[\"0\"]\n",
    "            else:\n",
    "                ans += left[\"1\"] * right[\"1\"]\n",
    "            left[s[i]] += 1\n",
    "            right[s[i]] -= 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        \n",
    "        n = len(s)\n",
    "        n0 = s.count('0')   # 0的总数目\n",
    "        n1 = n-n0           # 1的总数目\n",
    "\n",
    "        cnt0 = 0            # 左起0的数目\n",
    "        cnt1 = 0            # 左起1的数目\n",
    "        ans = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '0':\n",
    "                cnt0 += 1\n",
    "                ans += cnt1 * (n1-cnt1)     # 左边1的数目 * 右边1的数目\n",
    "            else:\n",
    "                cnt1 += 1\n",
    "                ans += cnt0 * (n0-cnt0)     # 左边0的数目 * 右边0的数目\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "       c=s.count('0')\n",
    "       print(c)\n",
    "       c1=0\n",
    "       c2=0\n",
    "       ans=0\n",
    "       n=len(s)\n",
    "       for x in s:\n",
    "         if x=='0':\n",
    "           ans+=c2*(n-c-c2)\n",
    "           c1+=1\n",
    "         else:\n",
    "           ans+=c1*(c-c1)\n",
    "           c2+=1\n",
    "       return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        n1=s.count('1')\n",
    "        res=0\n",
    "        cnt=0\n",
    "        for i in range(n):\n",
    "            if s[i]=='1':\n",
    "                res+=(i-cnt)*(n-n1-i+cnt)\n",
    "                cnt+=1\n",
    "            else:\n",
    "                res+=(n1-cnt)*cnt\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        total0 = total1 = 0\n",
    "        count0 = count1 = 0\n",
    "        last0 = last1 = 0\n",
    "        sLen = len(s)\n",
    "        dp = [0 for _ in range(sLen)]\n",
    "        ans = 0\n",
    "        for i in range(sLen):\n",
    "            if s[i] == '0':\n",
    "                total0 += 1\n",
    "                if i > 0 and s[i] != s[i-1]:\n",
    "                       \n",
    "                    last1 = count1\n",
    "                    count1 = 0\n",
    "                count0 += 1\n",
    "            else:\n",
    "                total1 += 1\n",
    "                \n",
    "                if i > 0 and s[i] != s[i-1]:\n",
    "                    \n",
    "                    last0 = count0\n",
    "                    count0 = 0\n",
    "                count1 += 1\n",
    "            \n",
    "            if i == sLen-1 or s[i] != s[i+1]:\n",
    "                if s[i] == '0' and last0 > 0:\n",
    "                    \n",
    "                    lastIdx = i-last1-count0\n",
    "                    if dp[lastIdx] == 0:\n",
    "                        dp[i] = last0*last1*count0\n",
    "                    else:\n",
    "                        tmp = dp[lastIdx]//last0\n",
    "                        dp[i] = dp[lastIdx]+ (count0-last0)*tmp\n",
    "                        dp[i] += (total0-count0)*last1*count0\n",
    "                    \n",
    "\n",
    "                elif s[i] == '1' and last1 > 0:\n",
    "                    \n",
    "                    lastIdx = i-last0-count1\n",
    "                    if dp[lastIdx] == 0:\n",
    "                        dp[i] = last1*last0*count1\n",
    "                    else:\n",
    "                        tmp = dp[lastIdx]//last1\n",
    "                        dp[i] = dp[lastIdx]+ (count1-last1)*tmp\n",
    "                        dp[i] += (total1-count1)*last0*count1\n",
    "                ans += dp[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        total0 = total1 = 0\n",
    "        count0 = count1 = 0\n",
    "        last0 = last1 = 0\n",
    "        sLen = len(s)\n",
    "        dp = [0 for _ in range(sLen)]\n",
    "\n",
    "        for i in range(sLen):\n",
    "            if s[i] == '0':\n",
    "                total0 += 1\n",
    "                if i > 0 and s[i] != s[i-1]:\n",
    "                       \n",
    "                    last1 = count1\n",
    "                    count1 = 0\n",
    "                count0 += 1\n",
    "                \n",
    "                #print(\"{}, total0:{}, total1:{}, curr0:{}, last0:{}, last1:{}\".format(i, total0, total1, count0, last0, last1))\n",
    "            else:\n",
    "                total1 += 1\n",
    "                \n",
    "                if i > 0 and s[i] != s[i-1]:\n",
    "                    \n",
    "                    last0 = count0\n",
    "                    count0 = 0\n",
    "                count1 += 1\n",
    "            \n",
    "                #print(\"{}, total0:{}, total1:{}, curr1:{}, last0:{}, last1:{},\".format(i, total0, total1,count1, last0, last1))\n",
    "            \n",
    "            if i == sLen-1 or s[i] != s[i+1]:\n",
    "                if s[i] == '0' and last0 > 0:\n",
    "                    \n",
    "                    lastIdx = i-last1-count0\n",
    "                    if dp[lastIdx] == 0:\n",
    "                        dp[i] = last0*last1*count0\n",
    "                    else:\n",
    "                        tmp = dp[lastIdx]//last0\n",
    "                        dp[i] = dp[lastIdx]+ (count0-last0)*tmp\n",
    "                        dp[i] += (total0-count0)*last1*count0\n",
    "                    #print(\"{}, total0:{}, total1:{}, curr0:{}, last0:{}, last1:{}, dp:{}\".format(i, total0, total1, count0, last0, last1, dp))\n",
    "                        \n",
    "                elif s[i] == '1' and last1 > 0:\n",
    "                    \n",
    "                    lastIdx = i-last0-count1\n",
    "                    if dp[lastIdx] == 0:\n",
    "                        dp[i] = last1*last0*count1\n",
    "                    else:\n",
    "                        tmp = dp[lastIdx]//last1\n",
    "                        dp[i] = dp[lastIdx]+ (count1-last1)*tmp\n",
    "                        dp[i] += (total1-count1)*last0*count1\n",
    "                    \n",
    "                    #print(\"{}, total0:{}, total1:{}, curr1:{}, last0:{}, last1:{},dp:{}\".format(i, total0, total1,count1, last0, last1, dp))\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "       n = len(s)\n",
    "       right0 = [0] * n\n",
    "       for i in range(n - 2, -1, -1):\n",
    "          right0[i] = right0[i + 1] + (1 if s[i + 1] == '0' else 0)\n",
    "       res = 0\n",
    "       left0 = 0\n",
    "       for i, v in enumerate(s):\n",
    "          if v == '1':\n",
    "             res += left0 * right0[i]\n",
    "          else:\n",
    "             res += (i - left0) * ((n - i - 1) - right0[i])\n",
    "             left0 += 1\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        cnt1 = [0]\n",
    "        cnt0 = [0]\n",
    "        for i in s:\n",
    "            if i == '0': \n",
    "                cnt0.append(cnt0[-1] + 1)\n",
    "                cnt1.append(cnt1[-1])\n",
    "            else:\n",
    "                cnt1.append(cnt1[-1] + 1)\n",
    "                cnt0.append(cnt0[-1])\n",
    "        ans = 0\n",
    "        for i in range(1, len(s) - 1):\n",
    "            if s[i] == '1':\n",
    "                ans += cnt0[i] * (cnt0[-1] - cnt0[i+1])\n",
    "            else:\n",
    "                ans += cnt1[i] * (cnt1[-1] - cnt1[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        t1=[]\n",
    "        t2=[]\n",
    "        q1=0\n",
    "        q2=0\n",
    "        c1=0\n",
    "        c2=0\n",
    "        lon=len(s)\n",
    "        for i in range(lon):\n",
    "            if s[i]=='1':\n",
    "                c1+=q2\n",
    "                q1+=1\n",
    "            else:\n",
    "                c2+=q1\n",
    "                q2+=1\n",
    "            t1.append(c1)\n",
    "            t2.append(c2)\n",
    "            \n",
    "\n",
    "        ans=0\n",
    "        for i in range(lon-1,1,-1):\n",
    "            if s[i]=='1':\n",
    "                ans+=t2[i-1]\n",
    "            else:\n",
    "                ans+=t1[i-1]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp1_0 = [0 for _ in range(n+1)]\n",
    "        dp1_1 = [0 for _ in range(n+1)]\n",
    "        dp2_0 = [0 for _ in range(n+1)]\n",
    "        dp2_1 = [0 for _ in range(n+1)]\n",
    "        dp3_0 = [0 for _ in range(n+1)]\n",
    "        dp3_1 = [0 for _ in range(n+1)]\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            if s[i-1] == '0':\n",
    "                dp1_0[i] = dp1_0[i-1] + 1\n",
    "                dp1_1[i] = dp1_1[i-1]\n",
    "            elif s[i-1] == '1':\n",
    "                dp1_0[i] = dp1_0[i-1]\n",
    "                dp1_1[i] = dp1_1[i-1] + 1\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            if s[i-1] == '0':\n",
    "                dp2_0[i] = dp2_0[i-1] + dp1_1[i-1]\n",
    "                dp2_1[i] = dp2_1[i-1]\n",
    "            elif s[i-1] == '1':\n",
    "                dp2_0[i] = dp2_0[i-1]\n",
    "                dp2_1[i] = dp2_1[i-1] + dp1_0[i-1]\n",
    "        for i in range(3, n+1):\n",
    "            if s[i-1] == '0':\n",
    "                dp3_0[i] = dp3_0[i-1] + dp2_1[i-1]\n",
    "                dp3_1[i] = dp3_1[i-1]\n",
    "            elif s[i-1] == '1':\n",
    "                dp3_0[i] = dp3_0[i-1]\n",
    "                dp3_1[i] = dp3_1[i-1] + dp2_0[i-1]\n",
    "        # print(dp1_0)\n",
    "        # print(dp1_1)\n",
    "        # print(dp2_0)\n",
    "        # print(dp2_1)\n",
    "        # print(dp3_0)\n",
    "        # print(dp3_1)\n",
    "        return dp3_0[-1] + dp3_1[-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
